import java.util.ArrayList;
public class EightPuzzle extends Problem
{
    private State  start;   
    private int heuristic;
   
    public EightPuzzle(String begin, int h)
    { 
        start = new State(begin);  
        heuristic = h;
    }
    
    public State getStartState( )
    {
        return start;
    }
    
    public  Node createNode(State s, int d, double g, double h, Node p)
    {
        return new EightPuzzleNode(s,d,g,h,p);
    }
    
    public  double getStepCost(Node n1, Node n2)
    {
       return 1;
    }
    
    //Implement this method for Qn 4: You may declare helper methods.
    public double getHeuristicValue(Node n)
    {  
        //You will need to grab the state from the node
        if (heuristic==1)
        {
            double misplaced = 0;
            State temp = n.state;
            String value = temp.getValue();
            if(value.charAt(0) != '1')
                misplaced++;
            if(value.charAt(1) != '2')
                misplaced++;
            if(value.charAt(2) != '3')
                misplaced++;
            if(value.charAt(3) != '4')
                misplaced++;
            if(value.charAt(4) != '5')
                misplaced++;
            if(value.charAt(5) != '6')
                misplaced++;
            if(value.charAt(6) != '7')
                misplaced++;
            if(value.charAt(7) != '8')
                misplaced++;
            if(value.charAt(8) != '0')
                misplaced++;
            return misplaced; //Do heuristic 1 here
        }
        else
        {
           double distance = 0;
           int count = 0;
           String x_value = "123123123";
           String y_value = "333222111";
           System.out.println(x_value);
           State temp = n.state;
           String value = temp.getValue();
           int locale0 = value.indexOf('0');
           int locale1 = value.indexOf('1');
           int locale2 = value.indexOf('2');
           int locale3 = value.indexOf('3');
           int locale4 = value.indexOf('4');
           int locale5 = value.indexOf('5');
           int locale6 = value.indexOf('6');
           int locale7 = value.indexOf('7');
           int locale8 = value.indexOf('8');
           int x_of0 = Integer.parseInt(x_value.substring(locale0, locale0 + 1));
           int y_of0 = Integer.parseInt(y_value.substring(locale0, locale0 + 1));
           int x_of1 = Integer.parseInt(x_value.substring(locale1, locale1 + 1));
           int y_of1 = Integer.parseInt(y_value.substring(locale1, locale1 + 1));
           int x_of2 = Integer.parseInt(x_value.substring(locale2, locale2 + 1));
           int y_of2 = Integer.parseInt(y_value.substring(locale2, locale2 + 1));
           int x_of3 = Integer.parseInt(x_value.substring(locale3, locale3 + 1));
           int y_of3 = Integer.parseInt(y_value.substring(locale3, locale3 + 1));
           int x_of4 = Integer.parseInt(x_value.substring(locale4, locale4 + 1));
           int y_of4 = Integer.parseInt(y_value.substring(locale4, locale4 + 1));
           int x_of5 = Integer.parseInt(x_value.substring(locale5, locale5 + 1));
           int y_of5 = Integer.parseInt(y_value.substring(locale5, locale5 + 1));
           int x_of6 = Integer.parseInt(x_value.substring(locale6, locale6 + 1));
           int y_of6 = Integer.parseInt(y_value.substring(locale6, locale6 + 1));
           int x_of7 = Integer.parseInt(x_value.substring(locale7, locale7 + 1));
           int y_of7 = Integer.parseInt(y_value.substring(locale7, locale7 + 1));
           int x_of8 = Integer.parseInt(x_value.substring(locale8, locale8 + 1));
           int y_of8 = Integer.parseInt(y_value.substring(locale8, locale8 + 1));
           double distance0 = Math.abs(x_of0 - 1) + Math.abs(y_of0 - 3);
           double distance1 = Math.abs(x_of1 - 2) + Math.abs(y_of1 - 3);
           double distance2 = Math.abs(x_of2 - 3) + Math.abs(y_of2 - 3);
           double distance3 = Math.abs(x_of3 - 1) + Math.abs(y_of3 - 2);
           double distance4 = Math.abs(x_of4 - 2) + Math.abs(y_of4 - 2);
           double distance5 = Math.abs(x_of5 - 3) + Math.abs(y_of5 - 2);
           double distance6 = Math.abs(x_of6 - 1) + Math.abs(y_of6 - 1);
           double distance7 = Math.abs(x_of7 - 2) + Math.abs(y_of7 - 1);
           double distance8 = Math.abs(x_of8 - 3) + Math.abs(y_of8 - 1);
           distance = (distance0 + distance1 + distance2 + distance3 + distance4 + distance5 + distance6 + distance7 + distance8);
           return distance; //Do heuristic 2 here 
        }
    }
    
    public  boolean isGoalState(State state)
    {
       return (state.getValue().equals("123456780")? true:false) ;
    }
}
